package hot_100;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class 单词拆分 {
    public static void main(String[] args) {
        List<String> wordDict = new LinkedList<>();
        Collections.addAll(wordDict, "leet", "code");
        boolean b = wordBreak("leetcode", wordDict);
        System.out.println(b);
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        Collections.sort(wordDict, (a, b) -> a.length() - b.length());
        for (int i = 0; i < n; i++) {
            for (String string : wordDict) {
                int h = string.length();
                if (i - h + 1 < 0)
                    break;
                if (s.substring(i - h + 1, i+1).equals(string)) {
                    dp[i + 1] = dp[i + 1] || dp[i + 1 - h];
                }
            }
        }
        return dp[n];
    }
}
